//输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 
//
// 示例 1: 
//
// 输入: n = 1
//输出: [1,2,3,4,5,6,7,8,9]
// 
//
// 
//
// 说明： 
//
// 
// 用返回一个整数列表来代替打印 
// n 为正整数 
// 
// Related Topics 数学 
// 👍 67 👎 0

package leetcode.editor.cn;

//Java：打印从1到最大的n位数
public class DaYinCong1daoZuiDaDeNweiShuLcof{
    public static void main(String[] args) {
        Solution solution = new DaYinCong1daoZuiDaDeNweiShuLcof().new Solution();
        
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //0不算在里面 所以要去掉
    int[] answer;
    char[] now_number, loop = {'0','1','2','3','4','5','6','7','8','9'};
    int nine_number_count = 0, now_answer_index = 0,left_start_border , n;
    public int[] printNumbers(int n) {
        this.n =n;
        answer = new int[(int) Math.pow( 10, n ) -1 ];
        now_number = new char[n];
        left_start_border = n -1;
        dfs( 0 );
        return answer;
    }

    //深度优先
    void dfs( int x ){
        //遍历到最底的那一个位了
        if ( x == n ){
            String s = String.valueOf( now_number ).substring(left_start_border);
            //去掉0这个数字
            if ( ! s.equals( "0" ) ){
                //使用Integer去掉了最左边的0
                answer[ now_answer_index++ ] = Integer.parseInt(s);
            }
            if ( n - left_start_border == nine_number_count){
                left_start_border --;
            }
            return;
        }
        for ( char i : loop ){
            if ( i == '9' ){
                nine_number_count++;
            }
            now_number[x] = i;
            dfs( x+1 );
        }
        //遍历过后，就把对应的nine_number恢复到原来的样子，每一层总是只有一个9，所以直接减去就行了，
        //这个循环的递归一层就会新增加一个9而已
        nine_number_count --;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
